#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<sys/time.h>
#include<time.h>
#define MAX 20
#define REPEAT 100000
// 递归
long int fib(int n){

    if((n == 1) || (n == 2)){
        return 1;
    }
    return fib(n-1) + fib(n-2);
} 

long int fib2(int n){

    if((n == 1) || (n == 2)){
        return 1;
    }
    long int fna = 1;
    long int fnb = 1;
    long int fnc;
    n--;
    while(n > 1){
        fnc = fna + fnb;
        fna = fnb;
        fnb = fnc;
        n--;
    }
    return fnc;
}
int
main(int argc,char * argv[]){

    int nval,rept;
    struct timeval time1;
    struct timeval time2;
    float intv1,intv2;
    for(nval = 1;nval <= MAX; nval++){

        long int fval;
        gettimeofday(&time1,NULL);
        for(rept = 0;rept < REPEAT;rept++){

            fval = fib(nval);
        }
        gettimeofday(&time2,NULL);
        intv1 = (time2.tv_sec - time1.tv_sec) + 1e-6 * (time2.tv_usec - time1.tv_usec);
        printf("fib (%2d) = %ld, time = %lf.\n",nval,fval,intv1);

        time1.tv_sec = 0,time1.tv_usec = 0;
        gettimeofday(&time1,NULL);
        for(rept = 0; rept < REPEAT; rept++){

            fval = fib2(nval);

        }
        gettimeofday(&time2,NULL);
        intv2 = (time2.tv_sec - time1.tv_sec) + 1e-6 * (time2.tv_usec - time1.tv_usec);
        printf("fib2 (%2d) = %ld, time = %lf.\n",nval,fval,intv2);

        printf("ratio = %f.\n",(float)intv1/intv2);
    }
    return EXIT_SUCCESS;
}